public class ShellSort {

    public static void sort(int[] arr) {
        int n = arr.length; //元素个数
        int gap = n / 2; //确定步长，每次取一半
        while (gap > 0) {
            for (int i = gap; i < n; i++) { //最后步长个元素分别与前面相同位置的元素比较
                int temp = arr[i]; //当前元素
                int j = i; //j为参与对比的元素位置
                //j必须大于步长
                //当前元素比前面相同步长位置的元素小，则交换位置
                while (j >= gap && arr[j - gap] > temp) {
                    //实际上是将对比元素插入到当前元素处
                    arr[j] = arr[j - gap];
                    j -= gap; //整个数组有可能有多组
                }
                //走到这里说面当前元素在前面找到了比自己小的元素，把当前元素插入到该位置
                arr[j] = temp;
            }
            gap /= 2; //每一次比较步长缩小一半
        }
    }

    // 测试代码
    public static void main(String[] args) {
        int[] arr = {20, 35, -15, 7, 55, 1, -22};

        System.out.println("原始数组：");
        printArray(arr);

        sort(arr);

        System.out.println("排序后数组：");
        printArray(arr);
    }

    // 打印数组的方法
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}